{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum String Length After Removing Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除子串后的字符串最小长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅由 <strong>大写</strong> 英文字符组成的字符串 <code>s</code> 。</p>\n",
    "\n",
    "<p>你可以对此字符串执行一些操作，在每一步操作中，你可以从 <code>s</code> 中删除 <strong>任一个</strong> <code>\"AB\"</code> 或 <code>\"CD\"</code> 子字符串。</p>\n",
    "\n",
    "<p>通过执行操作，删除所有&nbsp;<code>\"AB\"</code> 和 <code>\"CD\"</code> 子串，返回可获得的最终字符串的 <strong>最小</strong> 可能长度。</p>\n",
    "\n",
    "<p><strong>注意</strong>，删除子串后，重新连接出的字符串可能会产生新的&nbsp;<code>\"AB\"</code> 或 <code>\"CD\"</code> 子串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ABFCACDB\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>你可以执行下述操作：\n",
    "- 从 \"<em><strong>AB</strong></em>FCACDB\" 中删除子串 \"AB\"，得到 s = \"FCACDB\" 。\n",
    "- 从 \"FCA<em><strong>CD</strong></em>B\" 中删除子串 \"CD\"，得到 s = \"FCAB\" 。\n",
    "- 从 \"FC<strong><em>AB</em></strong>\" 中删除子串 \"AB\"，得到 s = \"FC\" 。\n",
    "最终字符串的长度为 2 。\n",
    "可以证明 2 是可获得的最小长度。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ACBBD\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>无法执行操作，字符串长度不变。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s</code> 仅由大写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-string-length-after-removing-substrings](https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-string-length-after-removing-substrings](https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ABFCACDB\"', '\"ACBBD\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        minLength = sys.maxsize\n",
    "        p1, p2 = 0, 0\n",
    "        currSum = 0\n",
    "        while p2 < len(nums):\n",
    "            currSum += nums[p2]\n",
    "            if currSum >= target:\n",
    "                while p1 <= p2 and currSum - nums[p1] >= target:\n",
    "                    currSum -= nums[p1]\n",
    "                    p1 += 1\n",
    "                minLength = min(minLength, p2-p1+1)\n",
    "            p2 += 1\n",
    "        return 0 if minLength == sys.maxsize else minLength\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "        \"\"\"\n",
    "        :type s: int\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = 0\n",
    "        r = 0\n",
    "        sum_all = 0\n",
    "        nums_len = len(nums)\n",
    "        minLength = nums_len + 1\n",
    "        while l < nums_len:\n",
    "            if r < nums_len and sum_all < s:\n",
    "                sum_all += nums[r]\n",
    "                r += 1\n",
    "            else:\n",
    "                sum_all -= nums[l]\n",
    "                l += 1\n",
    "\n",
    "            if sum_all >= s:\n",
    "                minLength = min(minLength, r - l)\n",
    "\n",
    "        if minLength == nums_len + 1:\n",
    "            return 0\n",
    "\n",
    "        return minLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while 'AB' in s or 'CD' in s:\n",
    "            tmp = \"\"\n",
    "            index = 0\n",
    "            while index < len(s):\n",
    "                if (index < (len(s) - 1)) and ((s[index] == 'A' and s[index + 1] == 'B') or (s[index] == 'C' and s[index + 1] == 'D')):\n",
    "                    index += 2\n",
    "                else:\n",
    "                    tmp += s[index]\n",
    "                    index += 1\n",
    "            s = tmp\n",
    "        return len(s)\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for x in s:\n",
    "            if stack and (stack[-1]+x == \"AB\" or stack[-1]+x == \"CD\"):\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(x)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        str = []\n",
    "        for i in s:\n",
    "            if str and (i == 'B' and str[-1] == 'A' or i == 'D' and str[-1] == 'C'):\n",
    "                str.pop()\n",
    "            else:\n",
    "                str.append(i)\n",
    "        return len(str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            s = s.replace(\"AB\", \"\").replace(\"CD\", \"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            s = s.replace(\"AB\", \"\").replace(\"CD\", \"\")\n",
    "        return len(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        # 这种和20题左右括号很类似，遍历序列，然后用栈顶和下一个元素匹配，满足条件的删掉，不满足条件的放进栈\n",
    "        # st = []\n",
    "        # for c in s:\n",
    "        #     if st and (c == 'B' and st[-1] == 'A' or c == 'D' and st[-1] == 'C'):  # 这里的st是为了当s第一个字母为B或者D的时候防止超出索引\n",
    "        #         st.pop()\n",
    "        #     else:\n",
    "        #         st.append(c)\n",
    "        # return len(st)\n",
    "\n",
    "\n",
    "        # 暴力解法\n",
    "        # while \"AB\" in s or \"CD\" in s:\n",
    "        #     s = s.replace(\"AB\", \"\").replace(\"CD\", \"\")\n",
    "        # return len(s)\n",
    "\n",
    "        # 栈\n",
    "        # dict1 = {\n",
    "        #     \"B\":\"A\",\n",
    "        #     \"D\":\"C\"\n",
    "        #     }\n",
    "        # stack = []\n",
    "        # for ch in s:\n",
    "        #     if ch in dict1:\n",
    "        #         if stack and dict1[ch] == stack[-1]:\n",
    "        #             stack.pop()\n",
    "        #         else:\n",
    "        #             stack.append(ch)  # 这步可不能忘啊\n",
    "        #     else:\n",
    "        #         stack.append(ch)\n",
    "        # return len(stack)\n",
    "\n",
    "\n",
    "        # dict1 = {\n",
    "        #     \"B\":\"A\",\n",
    "        #     \"D\":\"C\"\n",
    "        #     }\n",
    "        # stack = []\n",
    "        # for ch in s:\n",
    "        #     if ch in dict1 and stack and dict1[ch] == stack[-1]:\n",
    "        #         stack.pop()\n",
    "        #     else:\n",
    "        #         stack.append(ch)\n",
    "        # return len(stack)\n",
    "\n",
    "        dict = {\n",
    "            \"B\":\"A\",\n",
    "            \"D\":\"C\"\n",
    "            }\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch in dict:\n",
    "                if stack and dict[ch] == stack[-1]:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(ch)\n",
    "            else:\n",
    "                stack.append(ch)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        pair = {\n",
    "            'B': 'A',\n",
    "            'D': 'C'\n",
    "        }\n",
    "        for c in s:\n",
    "            if (len(stack) > 0 and\n",
    "                pair.get(c) == stack[-1]):\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "\n",
    "        # def find(s: str):\n",
    "        #     ans = \"\"\n",
    "        #     i = 0\n",
    "        #     while i < len(s):\n",
    "        #         if i + 2 <= len(s) and (s[i : i + 2] == \"AB\" or s[i : i + 2] == \"CD\"):\n",
    "        #             i += 2\n",
    "        #         else:\n",
    "        #             ans += s[i]\n",
    "        #             i += 1\n",
    "        #     return ans\n",
    "        # curr = \"\"\n",
    "        # while s != curr:\n",
    "        #     curr = s\n",
    "        #     s = find(curr)\n",
    "\n",
    "        # return len(s)\n",
    "\n",
    "        stack = list()\n",
    "        for i in s:\n",
    "            if len(stack) > 0:\n",
    "                if (stack[-1] == \"A\" and i == \"B\") or (stack[-1] == \"C\" and i == \"D\"):\n",
    "                    stack.pop()\n",
    "                else: stack.append(i)\n",
    "            else: stack.append(i)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        s_stack = ['a']\n",
    "        for each in s:\n",
    "            if (each == 'B' and s_stack[-1] == 'A') or (each == 'D' and s_stack[-1] == 'C'):\n",
    "                s_stack.pop(-1)\n",
    "            else:\n",
    "                s_stack.append(each)\n",
    "        return len(s_stack) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st = []\n",
    "        for i in s:\n",
    "            if st and ((i == 'B' and st[-1] == 'A') or (i == 'D' and st[-1] == 'C')):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(i)\n",
    "\n",
    "            \n",
    "\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while (\"AB\" in s or \"CD\" in s):\n",
    "            s = s.replace(\"AB\", \"\").replace(\"CD\", \"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        ll = []\n",
    "        for i in s:\n",
    "            if i not in ['A','B','C','D']:\n",
    "                ll.append(i)\n",
    "            else:\n",
    "                if len(ll) > 0 and ll[len(ll) - 1] == 'A' and i =='B':\n",
    "                    ll.pop()\n",
    "                elif len(ll) > 0 and ll[len(ll) - 1] == 'C' and i =='D':\n",
    "                    ll.pop()\n",
    "                else:\n",
    "                    ll.append(i)\n",
    "        return len(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while s.find('AB') != -1 or s.find('CD') != -1:\n",
    "            s = s.replace('AB', '')\n",
    "            s = s.replace('CD', '')\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st=deque()\n",
    "        for c in s:\n",
    "            if st and (c=='B' and st[-1]=='A' or c=='D' and st[-1]=='C'):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(c)\n",
    "\n",
    "        return len(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while 'AB' in s or 'CD' in s:\n",
    "            s = s.replace('AB', '')\n",
    "            s = s.replace('CD', '')\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "\n",
    "        while True:\n",
    "            quit = True\n",
    "            for i, c in enumerate(s):\n",
    "                if i + 1 < len(s):\n",
    "                    if c == 'A' and s[i + 1] == 'B':\n",
    "                        s = s[:i] + s[i + 2:]\n",
    "                        quit = False\n",
    "                        break\n",
    "                    elif c == 'C' and s[i + 1] == 'D':\n",
    "                        s = s[:i] + s[i + 2:]\n",
    "                        quit = False\n",
    "                        break\n",
    "            if quit: break\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while 'AB' in s or 'CD' in s:\n",
    "            if 'AB' in s:\n",
    "                s=s.replace('AB','')\n",
    "            if 'CD' in s:\n",
    "                s=s.replace('CD','')\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st = \"\"\n",
    "        for c in s:\n",
    "            st+=c\n",
    "            while len(st)>1 and (st[-2:]=='AB' or st[-2:]=='CD'):\n",
    "                st =st[:-2]\n",
    "        return len(st)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minLength(self, s: str) -> int:\n",
    "    while \"AB\" in s or \"CD\" in s:\n",
    "        s = s.replace(\"AB\", \"\").replace(\"CD\", \"\")\n",
    "    return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        l=len(s)\n",
    "        while True:\n",
    "            s=s.replace(\"AB\",\"\")\n",
    "            s=s.replace(\"CD\",\"\")\n",
    "            if len(s)==l:\n",
    "                break\n",
    "            else:\n",
    "                l=len(s)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st=[]\n",
    "        for c in s:\n",
    "            if st and(c=='B' and st[-1]=='A' or c=='D'and st[-1]=='C'):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(c)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        s_temp = s\n",
    "\n",
    "        while 'AB' in s_temp or 'CD' in s_temp:\n",
    "            s1 = s_temp.replace('AB', '')\n",
    "            s2 = s1.replace('CD', '')\n",
    "            s_temp = s2\n",
    "\n",
    "        return len(s_temp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        ans=[\"0\"]\n",
    "        for i in s:\n",
    "            if i==\"B\" and (ans[-1]==\"A\"):\n",
    "                ans.pop()\n",
    "            elif i==\"D\" and (ans[-1]==\"C\"):\n",
    "                ans.pop()\n",
    "            else:\n",
    "                ans.append(i)\n",
    "            \n",
    "        return len(ans)-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack=[]\n",
    "        for i in s:\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "                continue\n",
    "            if stack:\n",
    "                top=stack[-1]\n",
    "                if top==\"A\" and i==\"B\":\n",
    "                    stack.pop()\n",
    "                elif top==\"C\" and i==\"D\":\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st=[]\n",
    "        for v in s:\n",
    "            if st and ((v=='D' and st[-1]=='C') or (v=='B' and st[-1]=='A')):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(v)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while 'AB' in s or 'CD' in s:\n",
    "            s = s.replace('AB', '')\n",
    "            s = s.replace('CD', '')\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        for i in range(100):\n",
    "            if 'AB' or 'CD' in s:\n",
    "                s = s.replace('AB','')\n",
    "                s = s.replace('CD','')\n",
    "            else:\n",
    "                break\n",
    "        return len(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while True:\n",
    "            begin_len=len(s)\n",
    "            s=s.replace(\"AB\",\"\")\n",
    "            s=s.replace(\"CD\",\"\")\n",
    "            if len(s) == begin_len:\n",
    "                break\n",
    "        return len(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while True:\n",
    "            s1=s.replace('AB','').replace('CD','')\n",
    "            if len(s1)==len(s):\n",
    "                return len(s)\n",
    "            s=s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            s = s.replace(\"AB\", \"\")\n",
    "            s = s.replace(\"CD\", \"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while True:\n",
    "            if \"AB\" in s:\n",
    "                s = s.replace(\"AB\",\"\")\n",
    "            elif \"CD\" in s:\n",
    "                s = s.replace(\"CD\",\"\")\n",
    "            else:\n",
    "                return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            tmp = \"\".join(s.split(\"AB\"))\n",
    "            s = \"\".join(tmp.split(\"CD\"))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        \n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            s = s.replace(\"AB\",\"\").replace(\"CD\",\"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = [0]\n",
    "        for i in s:\n",
    "            if stack[-1] == 'A' and i =='B':\n",
    "                stack.pop()\n",
    "            elif stack[-1] == 'C' and i =='D':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)                \n",
    "        ans = ''.join(stack[1:])     \n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while 'AB' in s or 'CD' in s :\n",
    "            s=s.replace('AB','').replace('CD','')\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        \n",
    "        stk = []\n",
    "        for x in s:\n",
    "            if not stk:\n",
    "                stk.append(x)\n",
    "            elif stk[-1] == 'A' and x == 'B':\n",
    "                stk.pop()\n",
    "            elif stk[-1] == 'C' and x == 'D':\n",
    "                stk.pop()\n",
    "            else:\n",
    "                stk.append(x)\n",
    "        return len(stk)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "\n",
    "            s=s.replace(\"AB\",\"\")\n",
    "\n",
    "            s=s.replace(\"CD\",\"\")\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st=[]\n",
    "        for v in s:\n",
    "            if st and ((v=='D' and st[-1]=='C') or (v=='B' and st[-1]=='A')):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(v)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stc_1 = list(s)\n",
    "        i, l = 0, len(stc_1)\n",
    "        while i < l:\n",
    "            if stc_1[i] == 'A' and i < l - 1:\n",
    "                if stc_1[i+1] == 'B':\n",
    "                    del stc_1[i:i+2]\n",
    "                    i ,l = 0, len(stc_1)\n",
    "                else:\n",
    "                    i = i + 1\n",
    "            elif stc_1[i] == 'C' and i < l - 1:\n",
    "                if stc_1[i+1] == 'D':\n",
    "                    del stc_1[i:i+2]\n",
    "                    i ,l = 0, len(stc_1)\n",
    "                else:\n",
    "                    i = i + 1\n",
    "            else:\n",
    "                i = i + 1\n",
    "        return len(stc_1)    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        return len(s) if not (\"AB\" in s or \"CD\" in s) else self.minLength(s.replace(\"AB\", \"\").replace(\"CD\", \"\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st=[]\n",
    "        for v in s:\n",
    "            if st and ((v=='D' and st[-1]=='C') or (v=='B' and st[-1]=='A')):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(v)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        temp_list = [\"\"]\n",
    "        for i in s:\n",
    "            if i == \"B\" and temp_list[-1] == \"A\":\n",
    "                temp_list.pop(-1)\n",
    "                continue\n",
    "            elif i == \"D\" and temp_list[-1] == \"C\":\n",
    "                temp_list.pop(-1)\n",
    "                continue\n",
    "            else:\n",
    "                temp_list.append(i)\n",
    "        return len(temp_list)-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if stack and (stack[-1]+i=='AB' or stack[-1]+i=='CD'):\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            s = s.replace(\"AB\",\"\").replace(\"CD\",\"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minLength(self, s: str) -> int:\n",
    "    while \"AB\" in s or \"CD\" in s:\n",
    "        s = s.replace(\"AB\", \"\").replace(\"CD\", \"\")\n",
    "    return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        i = 0\n",
    "        while i < len(s)-1:\n",
    "            if s[i:i+2] == 'AB' or s[i:i+2] == 'CD':\n",
    "                s = s[:i] + s[i+2:]\n",
    "                i = 0\n",
    "            else:\n",
    "                i += 1\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        if \"AB\" in s or \"CD\" in s:\n",
    "            if \"AB\" not in s:\n",
    "                return self.minLength(s.replace(\"CD\",\"\"))\n",
    "            if \"CD\" not in s:\n",
    "                return self.minLength(s.replace(\"AB\",\"\"))\n",
    "            return min(self.minLength(s.replace(\"AB\",\"\")), self.minLength(s.replace(\"CD\",\"\")))\n",
    "        else:\n",
    "            return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while True:\n",
    "            s = s.replace(\"AB\", \"\")\n",
    "            s = s.replace(\"CD\", \"\")\n",
    "            if \"AB\" not in s and \"CD\" not in s:\n",
    "                break\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while 'AB' in s or 'CD' in s:\n",
    "            s = s.replace(\"AB\", \"\").replace(\"CD\", \"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        l=[]\n",
    "        for i in s:\n",
    "            l.append(i)\n",
    "            while len(l)>1:\n",
    "                if l[-1]=='B' and l[-2]=='A':\n",
    "                    del l[-1]\n",
    "                    del l[-1]\n",
    "                elif l[-1]=='D' and l[-2]=='C':\n",
    "                    del l[-1]\n",
    "                    del l[-1]\n",
    "                else:\n",
    "                    break\n",
    "        return len(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            s = s.replace(\"AB\",\"\").replace(\"CD\",\"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        for i in range(10000):\n",
    "            if 'AB' or 'CD' in s:\n",
    "                s = s.replace('AB','')\n",
    "                s = s.replace('CD','')\n",
    "            else:\n",
    "                break\n",
    "        return len(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if stack and stack[-1] == 'A' and i == 'B':\n",
    "                stack.pop()\n",
    "            elif stack and stack[-1] == 'C' and i == 'D':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while 'AB' in s or 'CD' in s:\n",
    "            if 'AB' in s:\n",
    "                s=s.replace('AB','')\n",
    "            if 'CD' in s:\n",
    "                s=s.replace('CD','')\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        dic = {'A':'B','C':'D'}\n",
    "        for i in s:\n",
    "            if stack and stack[-1] in dic:\n",
    "                if dic[stack[-1]]==i :\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                  stack.append(i)  \n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        dic = {'A': 'B', 'C': 'D'}\n",
    "        for i in s:\n",
    "            if stack and dic.get(stack[-1]) == i:\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while \"AB\" in s or \"CD\" in s:\n",
    "            s = s.replace(\"AB\",\"\")\n",
    "            s = s.replace(\"CD\",\"\")\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        rp = lambda x: x.replace('AB', '').replace('CD', '')\n",
    "        \n",
    "        while s != (nxt := rp(s)):\n",
    "            s = nxt\n",
    "        \n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            elif stack[-1] == 'A' and i == 'B':\n",
    "                stack.pop()\n",
    "            elif stack[-1] == 'C' and i == 'D':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = ''\n",
    "        for ch in s:\n",
    "            stack += ch\n",
    "            if len(stack) > 1 and stack[-2:] == 'AB':\n",
    "                stack = stack.replace('AB','')\n",
    "            elif len(stack) > 1 and stack[-2:] == 'CD':\n",
    "                stack = stack.replace('CD','')\n",
    "            else:\n",
    "                continue\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if st and (c == 'B' and st[-1] == 'A' or c == 'D' and st[-1] == 'C'):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(c)\n",
    "        return len(st)\n",
    "\n",
    "        # if not \"AB\" in s and  not \"CD\" in s:\n",
    "        #     return len(s)\n",
    "        # temp = s.split(\"AB\")\n",
    "        # temp = ''.join(temp).split(\"CD\")\n",
    "        # return  self.minLength(''.join(temp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        # n = len(s)\n",
    "        # i = 0\n",
    "        # cut = 0\n",
    "        # while i < n - 1:\n",
    "        #     if s[i : i + 2] == \"AB\" or s[i : i + 2] == \"CD\":\n",
    "        #         if i == 0:\n",
    "        #             cut += 2\n",
    "        #             i += 2\n",
    "        #             continue\n",
    "        #         p, q = i - 1, i + 2\n",
    "        #         while p >= 0 and q < n:\n",
    "        #             if (s[p] == \"A\" and s[q] == \"B\") or (s[p] == \"C\" and s[q] == \"D\"):\n",
    "        #                 p -= 1\n",
    "        #                 q += 1\n",
    "        #             else: break\n",
    "        #         i = q\n",
    "        #         cut += i - p - 1\n",
    "        #     else: i += 1\n",
    "        # return n - cut\n",
    "        def find(s: str):\n",
    "            ans = \"\"\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if i + 2 <= len(s) and (s[i : i + 2] == \"AB\" or s[i : i + 2] == \"CD\"):\n",
    "                    i += 2\n",
    "                else:\n",
    "                    ans += s[i]\n",
    "                    i += 1\n",
    "            return ans\n",
    "        curr = \"\"\n",
    "        while s != curr:\n",
    "            curr = s\n",
    "            s = find(curr)\n",
    "\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while True:\n",
    "            begin_len = len(s) \n",
    "            s = s.replace(\"AB\", \"\")\n",
    "            s = s.replace(\"CD\", \"\")\n",
    "            if len(s) == begin_len:\n",
    "                break\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        while True:\n",
    "            if 'AB' in s:\n",
    "                s = s.replace('AB', '')\n",
    "            if 'CD' in s:\n",
    "                s = s.replace('CD', '')\n",
    "            if 'AB' not in s and 'CD' not in s:\n",
    "                return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if st and (c == 'B' and st[-1] == 'A' or c == 'D' and st[-1] == 'C'):\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(c)\n",
    "        return len(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        \n",
    "        while  'AB' in s or  'CD' in s:\n",
    "            s=s.replace('AB',\"\").replace('CD','')\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        res = [0] * len(s)\n",
    "        top = -1\n",
    "\n",
    "        for i in s:\n",
    "            if top >= 0 and ((res[top] == 'A' and i == 'B') or (res[top] == 'C' and i == 'D')):\n",
    "                top -= 1\n",
    "            else:\n",
    "                top += 1\n",
    "                res[top] = i\n",
    "\n",
    "        return top + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        s += '0'\n",
    "        i, l = 0, []\n",
    "        \n",
    "        \n",
    "        while i < len(s) - 1:\n",
    "            \n",
    "            if s[i: i+2] in \"AB1CD\":\n",
    "                i += 2\n",
    "            else:\n",
    "                if l and l[-1] + s[i] in \"AB1CD\":\n",
    "                      l.pop()\n",
    "                else:\n",
    "                    l.append(s[i])\n",
    "                i += 1\n",
    "                   \n",
    "                 \n",
    "        return len(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        \n",
    "        while s != \"\":\n",
    "            check = 0\n",
    "            for i in range(0, len(s)-1):\n",
    "                if s[i:i+2] == \"AB\" or s[i:i+2] == \"CD\":\n",
    "                    s = s[0:i]+s[i+2:]\n",
    "                    check = 1\n",
    "                    break\n",
    "            if check == 0:\n",
    "                return len(s)\n",
    "        \n",
    "        if s == \"\":\n",
    "            return 0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        tem = []\n",
    "        for c in s:\n",
    "            if tem and (c == \"B\" and tem[-1] == \"A\" or c == \"D\" and tem[-1] == \"C\"):\n",
    "                tem.pop()\n",
    "            else:\n",
    "                tem.append(c)\n",
    "        return len(tem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLength(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if len(stack) <= 0:\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if (stack[-1] == 'A' and c == 'B') or (stack[-1] == 'C' and c == 'D'):\n",
    "                    stack.pop(-1)\n",
    "                else:\n",
    "                    stack.append(c)\n",
    "        return len(stack)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
